package mianshi.huawei.medium;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;

/**
 * 编写一个程序，将输入字符串中的字符按如下规则排序。
 * 规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
 * 如，输入： Type 输出： epTy
 * 规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
 * 如，输入： BabA 输出： aABb
 * 规则 3 ：非英文字母的其它字符保持原来的位置。
 * 如，输入： By?e 输出： Be?y
 */
public class 字符串排序 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while (true) {
            if ((line = bufferedReader.readLine()) != null) {
                sortString(line);
            } else {
                break;

            }
        }

    }

    public static void sortString(String str) {
        Map<Character, Queue<Character>> map = new TreeMap<>();
        for (int i = 0; i < 26; i++) {
            Queue<Character> queue = new LinkedList<>();
            map.put((char)(i + 'a'), queue);
        }
        //将字母都装入字符对应的队列中
        for (int i = 0; i < str.length(); i++) {
            char c1 = str.charAt(i);
            if (Character.isLetter(c1)) {
                char c2 = (char) (c1 + 32);
                //小写字母
                if (map.containsKey(c1) ) {
                    map.get(c1).offer(c1);
                }
                //大写字母
                if (map.containsKey(c2)) {
                    map.get(c2).offer(c1);
                }

            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (Character.isLetter(c)) {
                stringBuilder.append(getChar(map));
            } else {
                stringBuilder.append(c);
            }
        }

        System.out.println(stringBuilder.toString());

    }

    /**
     * 将字母一个一个按要求的顺序弹出
     * @param map
     * @return
     */
    public static Character getChar(Map<Character, Queue<Character>> map) {
        for (Character character : map.keySet()) {
            Queue<Character> queue = map.get(character);
            while (!queue.isEmpty()) {
                return queue.poll();
            }
        }
        return null;
    }
}
